package algorithm.disjoint.union;

import java.util.Arrays;

/**
 * 项目名称: god
 * 包 名 称: algorithm.disjoint.union
 * 类 名 称: UnionFindQuickUnionSize
 * 类 描 述: TODO
 * 创建时间: 2020/6/30 11:21 上午
 * 创 建 人: Justice
 * 基于size的优化
 */
public class UnionFindQuickUnionSize extends UnionFindQuickUnion {
    // 以p1为根结点的树，有多少个元素
    private int[] sizes;

    public UnionFindQuickUnionSize(int capacity) {
        super(capacity);
        sizes = new int[capacity];
        // 默认一个元素
        Arrays.fill(sizes, 1);
    }

    // 将v1的根节点嫁接到v2的根节点上
    public void union(int v1, int v2) {
        int p1 = find(v1 );
        int p2 = find(v2);
        if (p1 == p2) return;
        if (sizes[p1] < sizes[p2]) {
            parents[p1] = p2;
            sizes[p2] += sizes[p1];
        } else {
            parents[p2] = p1;
            sizes[p1] += sizes[p2];
        }
    }
}
